#include <vector>
#include <string>
#include <cstring>

using namespace std;

// 牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份
// 密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：
// 密匙 b 的长度不超过密匙 a 的长度。
// 对于任意 0 <= i < length(b)，有b[i+1] - b[i] == a[i+1] - a[i]
// 现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组
// 请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙
// 数组 a 和数组 b 中的元素个数均不超过 10^5
// 1 <= m, n <= 1000
// 测试链接 : https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932

class Solution 
{
private:
	// 如果将来增加了数据量，就改大这个值
    static const int MAXN = 2000001;
    int tree[MAXN][12];
    int pass[MAXN];
    int cnt;

    void build()
    {
        cnt = 1;
    }

	// '0' ~ '9' 10个 0 ~ 9
	// '#' 10
	// '-' 11
    int path(char ch)
    {
        if(ch == '#') return 10;
        else if(ch == '-') return 11;
        else return ch - '0';
    }

    void insert(string& word)
    {
        int cur = 1;
        ++pass[cur];
        for(int i = 0, index; i < word.size(); ++i)
        {
            index = path(word[i]);
            if(tree[cur][index] == 0)
            {
                tree[cur][index] = ++cnt;
            }
            cur = tree[cur][index];
            ++pass[cur];
        }
    }

    int count(string& prefix)
    {
        int cur = 1;
        for(int i = 0, index; i < prefix.size(); ++i)
        {
            index = path(prefix[i]);
            if(tree[cur][index] == 0) return 0;
            cur = tree[cur][index];
        }
        return pass[cur];
    }

    void clear()
    {
        for(int i = 1; i <= cnt; ++i)
        {
            memset(tree[i], 0, sizeof(tree[i]));
            pass[i] = 0;
        }
    }

public:
    vector<int> countConsistentKeys(vector<vector<int> >& b, vector<vector<int> >& a) 
    {
        build();
        string s;
        // [3,6,50,10] -> "3#44#-40#"
        for(auto& nums : a)
        {
            s.clear();
            for(int i = 1; i < nums.size(); ++i)
            {
                s.append(to_string(nums[i] - nums[i - 1]) + "#");
            }
            insert(s);
        }

        vector<int> ans(b.size());
        for(int i = 0; i < b.size(); ++i)
        {
            auto& nums = b[i];
            s.clear();
            for(int i = 1; i < nums.size(); ++i)
            {
                s.append(to_string(nums[i] - nums[i - 1]) + "#");
            }
            ans[i] = count(s);
        }
        clear();
        return ans;
    }
};